
/**
*实验六 - 用栈实现迷宫求解算法
*学号： 201531002134
*班级： 软工1601
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

int flag = 0;  //标志位，看迷宫是否能够出去

int Maze[10][10]={
1,1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,0,0,1,1,0,0,1,
1,0,1,1,1,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,1,
1,0,1,0,0,0,1,0,0,1,
1,0,1,1,1,0,1,1,0,1,
1,1,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1
};

typedef struct{
    int x;
    int y;
}Pos;

typedef struct{
    int ord;        //通道块在路径上的“序号”
    Pos seat;       //通道块在迷宫中的坐标位置
    int di;         //从此通道走向下一通道的方向
}Node;

typedef struct{
    Node *base;
    Node *top;
    int stacksize;
}SqStack;

int InitStack(SqStack &s);   //初始化空栈
int isEmpty(SqStack &s);  //判断栈是否为空
int Push(SqStack &s, Node e);  //进栈,e表示进栈元素
int Pop(SqStack &s, Node &e);  //出栈,e是出栈元素
void clearStack(SqStack &s);   //将栈清空
void printMaze();               //打印迷宫
void nextPos(Pos &curpos,int direct);  //下一个位置
void mazePath();

int main()
{
    printMaze();
    mazePath();
    if (flag == 0)
        printf("该迷宫不能走出去!\n");
    return 0;
}

int InitStack(SqStack &s)
{
    s.base = (Node *)malloc(STACK_INIT_SIZE*sizeof(Node));
    if (!(s.base))
        return 0;
    s.top = s.base; //初始化栈
    s.stacksize = STACK_INIT_SIZE;
    return 1;
}

int isEmpty(SqStack &s)
{
    if ( s.top == s.base)
        return 1;
    else
        return 0;
}

int Push(SqStack &s, Node e)
{
    //检查栈是否已满
    if (s.top - s.base >= s.stacksize)
    {
        s.base = (Node *)realloc(s.base , (s.stacksize+STACKINCREMENT)*sizeof(Node));
        if (!s.base)
            return 0;
        s.top = s.base + s.stacksize;
        s.stacksize += STACKINCREMENT;
    }
    s.top->di = e.di;
    s.top->seat.x = e.seat.x;
    s.top->seat.y = e.seat.y;
    s.top->ord = e.ord;
    s.top++ ;
    return 1;
}

int Pop(SqStack &s, Node &e)
{
    //判断栈是否为空
    if (s.top == s.base)
        return 0;
    --s.top;
    e.di = s.top->di;
    e.ord = s.top->ord;
    e.seat.x = s.top->seat.x;
    e.seat.y = s.top->seat.y;
    return 1;
}

void clearStack(SqStack &s)
{
    s.top = s.base;
    s.stacksize = 0;
}

void printMaze()
{
    int i,j;
    printf("打印迷宫：\n");
    for (i=0;i<10;i++)
    {
        for(j=0;j<10;j++)
        {
            printf("%d",Maze[i][j]);
        }
        printf("\n");
    }
}

void nextPos(Pos &cpos,int direct)
{
    switch (direct)
    {
    case 1:                 //向右
        cpos.x ++;
        break;
    case 2:                 //向下
        cpos.y ++;
        break;
    case 3:                 //向左
        cpos.x --;
        break;
    case 4:
        cpos.y --;        //向上
        break;

    }
}

void mazePath()
{
    int curstep =1 ,i,j;  //当前步数，初始化为第1步
    int mark[10][10] = {0};
    int result[10][10] = {0};
    SqStack s;    //可以通过的路径栈
    Node e; //数据结点
    Pos curpos;    //当前位置是，初始化为（1，1）
    curpos.x = 1;
    curpos.y = 1;

    InitStack(s);

    do{
        if ( Maze[curpos.x][curpos.y]==0 && mark[curpos.x][curpos.y]==0 )  //如果这个位置可以通过
        {
            mark[curpos.x][curpos.y] = 1;  // 在标志的数组上留下该位置足迹，标志为走过
            printf("迷宫状态%d,标志状态%d\n",Maze[curpos.x][curpos.y],mark[curpos.x][curpos.y]==0);

            printf("第%d步,pos(%d,%d)  -- 可以通过\n",curstep,curpos.x,curpos.y);

            e.ord = curstep; //第几步
            e.seat.x = curpos.x;
            e.seat.y = curpos.y;
            e.di = 1; //向右走
            Push(s,e);  //当前状态入栈

            if ((curpos.x == 8)&&(curpos.y ==8))  //如果到达终点
            {
                flag = 1;
                printf("走出迷宫的一条路径是：\n");
                for (i=0;i<10;i++)
                {
                    for(j=0;j<10;j++)
                    {
                        result[i][j] = Maze[i][j];
                    }
                }
                while(!isEmpty(s))
                {
                    Pop(s,e);
                    result[e.seat.x][e.seat.y] = 35;
                }

                for (i=0;i<10;i++)
                {
                    for(j=0;j<10;j++)
                    {
                        if (result[i][j] == 35 )
                            printf("%c",result[i][j]);
                        else
                            printf("%d",result[i][j]);
                    }
                    printf("\n");
                }

                clearStack(s);
                return;
            }
            else
                printf("还没到终点\n");

            nextPos(curpos,1);
            curstep++;
        }
        else //当前位置不能通过
        {
            printf("第%d步,pos(%d,%d)  -- 不能通过\n",curstep,curpos.x,curpos.y);

            if (!isEmpty(s))
            {
                printf("不能通过的点出栈！\n");
                Pop(s,e);

                while(e.di ==4 && !isEmpty(s))  //当四个方向都不能通过时
                {
                    mark[e.seat.x][e.seat.y] =1;
                    Pop(s,e);
                }//while

                if(e.di < 4)
                {
                    e.di++;
                    printf("换个方向入栈,方向是%d\n",e.di);
                    Push(s,e);  // 换下一个方向探索

                    curpos.x = e.seat.x;
                    curpos.y = e.seat.y;
                    nextPos(curpos,e.di);   //设定当前位置是该新方向上的相邻块
                }//if
            }//if
        }//else
    }while( !isEmpty(s));
}



